https://leetcode.cn/problems/minimum-window-substring/submissions/560519047/


class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """

        # 辅助函数，检查当前窗口是否包含 t 中的所有字符
        def isValid(s_map, t_map):
            for k, v in t_map.items():
                if k not in s_map or s_map[k] < v:
                    return False
            return True

        left, right = 0, 0  # 初始化左右指针
        t_map = {}  # 记录 t 中每个字符的出现次数
        for c in t:
            t_map[c] = t_map.get(c, 0) + 1  # 统计 t 中每个字符的频率

        s_map = {}  # 记录当前窗口中每个字符的出现次数
        min_substr = None  # 最小覆盖子串
        min_len = float('inf')  # 最小子串长度初始化为无穷大

        while right <= len(s):  # 右指针遍历到字符串末尾
            if not isValid(s_map, t_map):  # 如果当前窗口不包含 t 中的所有字符
                if right == len(s):  # 如果右指针已经到达字符串末尾，退出循环
                    break
                c = s[right]  # 获取当前右指针指向的字符
                s_map[c] = s_map.get(c, 0) + 1  # 更新当前窗口中的字符计数
                right += 1  # 右指针向右移动
            else:  # 当前窗口包含 t 中的所有字符
                if right - left < min_len:  # 如果当前窗口更小
                    min_substr = s[left:right]  # 更新最小覆盖子串
                    min_len = right - left  # 更新最小子串长度
                c = s[left]  # 获取当前左指针指向的字符
                s_map[c] -= 1  # 更新当前窗口中的字符计数
                left += 1  # 左指针向右移动

        return min_substr if min_substr is not None else ""  # 返回结果

# 示例
# s = "ADOBECODEBANC"
# t = "ABC"
# 输出: "BANC"